The present invention relates to networks of data processing systems and more particularly to contention based networks.
As wireless technology becomes more ubiquitous, the interest in wireless networks which may carry both voice and data traffic has increased. To address the need for standardized operations in wireless networks, the Institute of Electrical and Electronics Engineers (IEEE) proposed the IEEE 802.11 Standard for Wireless LAN Medium Access Control and Physical Layer specifications (the 802.11 standard). The 802.11 standard provides a framework for wireless stations to intercommunicate utilizing a shared access wireless communications medium.
The 802.11 standard provides two mechanisms for a wireless station to access the shared wireless communication medium. These two mechanisms are a contention free arbitration mechanism and a contention based arbitration mechanism. Both of these access methods are supported concurrently by the 802.11 standard.
The contention free arbitration mechanism utilizes a point coordinator function (PCF) to control access to the shared communications medium. When a PCF is established, the PCF polls registered wireless stations for communications and provides communication medium access to the stations based on the results of this polling. Thus, the PCF may prioritize messages within the stations which are included in the polling sequence. For a wireless station to be included in the PCF polling sequence, the wireless station must support PCF operations and must make itself known to the PCF.
The contention based mechanism utilizes a random back-off period to provide fairness in accessing the shared communications medium. In the contention based period, each station monitors the shared communications medium and determines if the medium has been silent for a predefined period of time. If so, then the stations waits a random amount of time longer and, if the communications medium is still silent, transmits its message on the medium.
The interaction of the contention-free and contention based arbitration mechanisms may be seen in FIG. 1. As seen in FIG. 1, in order to allow a PCF to take control of the wireless medium, a PCF monitors the wireless medium for an amount of time called the PCF inter-frame spacing (PIFS) period. If the wireless medium is idle for the PIFS period, then the PCF gains access to the medium and takes control of the medium to become master of the medium. If a PCF is established as a master, then a contention-free period is used for the round-robin polling of the PCF compatible stations which are registered with the PCF. Thus, the PIFS period may be utilized by a PCF to gain prioritized access to the wireless medium to implement the contention-free arbitration of the wireless medium.
FIG. 1 also illustrates the contention based access to the wireless medium. As is seen in FIG. 1, the stations utilizing the distributed coordination function (DCF) determine whether the wireless communication medium is idle by monitoring the medium and determining that the medium is idle for a period of time referred to as the DCF inter-frame spacing (DIFS) period. The DIFS period is longer than the PIFS period. The stations using DCF also utilize a random back-off time which is added to the DIFS period to implement a Carrier Sense Multiple Access with Collision Avoidance (CSMA/CA) mechanism. For a station to gain access to the wireless medium, the station must sense that the wireless medium is idle for a period of time equal to the DIFS period plus the random back-off time.
Thus, by creating two, non-overlapping idle times, the 802.11 standard provides for prioritized access by a PCF while still allowing for contention based access. Such a two tiered system may be especially well suited to networks which carry both voice and data. Voice communications typically are more time sensitive than data communications in that a voice transmission may not tolerate long delays between communications whereas data communications typically are less sensitive to such delays for any given group of communications. Voice communications may, therefore, utilize the point coordinated communications (i.e., contention-free) to assure that the voice communications will be handled in a manner which may provide acceptable data rates and inter-communication delays so as to provide acceptable voice communications to an end user. Distributed coordination function communications (i.e., contention based) could then be utilized for less time critical data communications.
While the use of PCF and DCF communications within a network may theoretically provide suitable performance for a hybrid voice/data network, such performance may be based on an assumption that all stations utilizing voice communications support point coordinated communications. However, point coordinated communications may not be supported by all stations sharing a wireless communications medium. Thus, voice traffic for such stations may be required to be transmitted utilizing the contention based DCF communications which may result in a loss of performance for such voice communications.
In light of the above discussion, a need exists for improvements in contention based mechanisms for accessing a shared communication medium.
The present invention may provide systems and methods for providing prioritized access to a shared communication medium where the shared medium is accessed utilizing a contention based access arbitration mechanism and a contention-free arbitration mechanism. The contention based mechanism has an associated first time duration during which the shared communication medium must be idle for a station to access the shared communication medium utilizing the contention based access arbitration mechanism. The contention-free mechanism has associated with it a second time duration during which the shared communication medium must be idle to access the shared communication medium utilizing the contention-free arbitration mechanism. The first time duration is greater than the second time duration. Priority access to the shared communication medium may then be provided by determining a priority time duration between the second time duration and the first time duration for a station seeking contention based priority access to the shared communication medium and accessing the shared communication medium if the shared communication medium is idle for the priority time duration.
By utilizing the time between the contention-free period and the contention period, this first embodiment of the present invention may provide prioritized access over other contention based accesses without interfering with either the contention based access or the contention-free access. Furthermore, stations in the network which do not support contention-free access may utilize the present invention for priority access utilizing a contention based approach. Thus, the present invention may provide priority access to systems without requiring the stations to support contention-free access.
In a particular aspect of the first embodiment of the present invention, the determination of a priority time duration may be carried out by determining a priority time duration between the second time duration and the first time duration based on a priority of a station seeking access to the shared communication medium. Furthermore, this prioritzed access may be provided by determining a pseudo-random value between a minimum random value and a maximum random value, multiplying the pseudo-random value by a priority slot time to provide a random back-off time and adding the random back-off time to the second time duration to provide the priority time duration. Preferably, the sum of the second time duration and the product of the maximum random value and the priority slot time is less than the first time duration. Thus, collision avoidance may be provided to the prioritized access utilizing a random back-off procedure in the period between the contention-free period and the contention based period.
In particular embodiments of the present invention where all stations supporting the prioritized access are of equal priority, the minimum random value may be zero. However, the minimum random value may also be based on the priority of the station seeking access to the shared communication medium. Similarly, the maximum random value may be based on the priority of the station seeking access to the shared communication medium.
In a preferred embodiment of the present invention the shared communication medium is a wireless communication medium. In a particularly preferred embodiment, the contention based arbitration mechanism and the contention-free based arbitration mechanism comprise an IEEE 802.11 standard compliant network. In such an embodiment, the step of determination of a priority time duration may be made by determining a priority time duration between the PIFS period and the DIFS period.
Furthermore, the determination of the priority time duration may be made by determining a pseudo-random value in the interval from 0 to CW, where CW is a value between the 802.11 parameters aCWmin and aCWmax. The pseudo-random value may be multiplied by a priority slot time which is less than the 802.11 parameter aSlotTime to provide a PIFS random back-off time. The PIFS random back-off time may then be added to the PIFS period to provide the priority time duration. Preferably, the sum of the PIFS period and the product of aCwmax and the priority slot time is less than the DIFS period.
The determination of a pseudo-random value may also be determined in the interval from aPIFSPriority_x_CWmin to CW, where aPIFS Priority_CWmin is a value associated with a priority of a message to be transmitted on the shared communications medium and where CW is a value between aCWmin and aCWmax. The value of aPIFSPriority_x_CWmin may be based on the information content of the message to be transmitted on the shared communication medium. The value of aPIFSPriority_x_CWmin may also be based on the priority of the station seeking access to the shared communication medium. Thus, through the use of aPIFSPriority_x_CWmin, different priority levels within the time period between the PIFS period and the DIFS period may be provided. The higher the value of aPIFSPriority_x_CWmin, the lower the priority of the message.
In an alternative embodiment of the present invention, prioritized access in an IEEE 802.11 contention based arbitration mechanism for a shared communication medium utilizing a random back-off time after a DIFS time interval may be provided by establishing a priority parameter defining a lower bound of an interval from which the random back-off time is selected. The interval from which the random back-off time is then selected to be from the priority parameter to CW and a random back-off time selected from the selected interval. As with the previous embodiment, the priority parameter may be set based on a priority associated with the type of information to be transmitted on the shared access communication medium.
In a further embodiment of the present invention, a communications station for communicating in a network having a shared communication medium utilizing a contention based access arbitration mechanism and a contention-free arbitration mechanism is provided. A first time duration is defined during which the shared communication medium must be idle for a station to access the shared communication medium utilizing the contention based access arbitration mechanism and a second time duration defined during which the shared communication medium must be idle to access the shared communication medium utilizing the contention-free arbitration mechanism. The communication station includes a transceiver configured so as to communicate with the shared communication medium and a sense circuit, operably associated with the transceiver, which is configured so as to sense if the shared communication medium is idle. A medium access controller, operably associated with the transceiver and the sense circuit, is configured so as to determine a priority time duration between the second time duration and the first time duration for the station and to access the shared communication medium utilizing the transceiver to take control of the shared access communication medium if the sense circuit indicates that the shared communication medium is idle for the priority time duration.
In a further embodiment, the medium access controller is further configured to determine the priority time duration between the second time duration and the first time duration based on a priority of a message to be transmitted on the shared communication medium.
The medium access controller may further include a pseudo-random number generator configured to determine a pseudo-random value between a minimum random value and a maximum random value, a multiplier configured to multiply the pseudo-random value by a priority slot time to provide a random back-off time, and an adder configured to add the random back-off time to the second time duration to provide the priority time duration. Furthermore, the minimum random value may be zero. Alternatively, the minimum random value is based on the priority of the station. Similarly, the maximum random value may be based on the priority of the station.
Preferably, the shared communication medium is a wireless communication medium. In particular, the contention based arbitration mechanism and the contention-free based arbitration mechanism comprise an IEEE 802.11 standard compliant network in which case, the medium access controller may be an IEEE 802.11 compliant medium access controller.
In such an IEEE 802.11 embodiment, the medium access controller may be configured to determine a priority time duration between the PIFS period and the DIFS period. Furthermore, the medium access controller may include a pseudo-random number generator configured to provide a pseudo-random value in the interval from 0 to CW where CW is a value between aCWmin and aCWmax, a multiplier configured to multiply the pseudo-random value by a priority slot time which is less than aSlotTime to provide a PIFS random back-off time and, an adder configured to add the PIFS random back-off time to the PIFS period to provide the priority time duration.
Furthermore, the pseudo-random number generator may be configured to generate a pseudo-random value in the interval from aPIFSPriority_x_CWmin to CW rather than 0 to CW, where aPIFSPriority_x_Cwmin is a value associated with a priority of a message to be transmitted on the shared communications medium and where CW is a value between aCWmin and aCWmax. The value of aPIFSPriorityx_x_CWmin may be based on the priority of the station seeking access to the shared communication medium. The value of aPIFSPriority_x_CWmin may also be based on the information content of a message to be transmitted on the shared communication medium.
In a further alternative embodiment of the present invention, a communications station which provides prioritized access in an IEEE 802.11 contention based arbitration mechanism for a shared communication medium utilizing a random back-off time after a DIFS time interval includes a transceiver configured so as to communicate with the shared communication medium and a sense circuit operably associated with the transceiver and configured so as to sense if the shared communication medium is idle. A medium access controller is operably associated with the transceiver and the sense circuit and configured so as to establish a priority parameter defining a lower bound of an interval from which the random back-off time is selected. The interval from which the random back-off time is then selected to be from the priority parameter to CW and a random back-off time selected from this interval. The priority parameter may be set based on a priority associated with the type of information to be transmitted on the shared access communication medium.
By providing the ability to have priority access for contention based access to a shared communication medium, the present invention may facilitate the use of such networks for both voice and data communications. Furthermore, voice communications may benefit from improved performance even in systems where stations do not support contention-free access to the communications because of the provision of contention based priority.